import java.util.ArrayList;
import java.util.List;

public class PancakeSorting {
    /**
     *给你一个整数数组 arr ，请使用 煎饼翻转 完成对数组的排序。
     * 一次煎饼翻转的执行过程如下：
     * 选择一个整数 k ，1 <= k <= arr.length
     * 反转子数组 arr[0...k-1]（下标从 0 开始）
     * 例如，arr = [3,2,1,4] ，选择 k = 3 进行一次煎饼翻转，反转子数组 [3,2,1] ，得到 arr = [1,2,3,4] 。
     * 以数组形式返回能使 arr 有序的煎饼翻转操作所对应的 k 值序列。
     * 任何将数组排序且翻转次数在10 * arr.length 范围内的有效答案都将被判断为正确。
     * 链接：https://leetcode-cn.com/problems/pancake-sorting
     * @param arr
     * @return
     */
    public List<Integer> pancakeSort(int[] arr) {
        List<Integer> ans = new ArrayList<Integer>();

        for (int i=0;i<arr.length-1;i++){
            int min = Integer.MAX_VALUE;
            int k = i;
            for (int j=i;j<arr.length;j++){
                if (min>arr[j]){
                    min = arr[j];
                    k = j;
                }
            }
            ans.add(k+1);
            ans.add(i+1);


        }

        
        return ans;

    }
}
